package sort

import (
	"math"
	"strconv"
)

// 从个位开始位排序，依次存入桶中
// 按照顺序出桶到新数组，遍历新数组

// BaseSort 基数排序
func BaseSort(arr []int) []int {
	// 得到最大的位数
	maxBit := 0
	for _, val := range arr {
		if bit := NumBit(val); bit > maxBit {
			maxBit = bit
		}
	}

	arrTemp := arr[:]
	container := make(map[int][]int)
	for i := 1; i <= maxBit; i++ {
		// 入桶
		for _, val := range arrTemp {
			num := getBit(val, i)
			container[num] = append(container[num], val)
		}

		// 出桶
		arrTemp = []int{}
		for j := 0; j < 10; j++ {
			for _, val := range container[j] {
				arrTemp = append(arrTemp, val)
			}
			container[j] = []int{}
		}
	}

	return arrTemp
}

// 获取数字的长度
func NumBit(num int) int {
	bit := 0
	curNum := num

	for (curNum / 10) != 0 {
		bit++
		curNum /= 10
	}

	return bit + 1
}

// 获取数字的某一位
func getBit(num int, bit int) int {
	if int(math.Pow(10, float64(bit)-1)) > num {
		return 0
	}

	str := strconv.Itoa(num)
	numStr := string(str[len(str)-bit])
	res, _ := strconv.Atoi(numStr)

	return res
}
